package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * 全排列本身就是使用 used 数组进行去重
 * 如果数组中本身包含重复元素，那么很自然的就是用 uesd 数组 + 对数组本身进行排序进行去重
 */

public class PermutationsII {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            int[] used = new int[nums.length];
            backtracking(nums, used);
            return res;
        }

        private void backtracking(int[] nums, int[] used){
            if(path.size() == nums.length){
                res.add(new ArrayList<>(path));
                return;
            }

            for(int i = 0; i < nums.length; i++){
                if(used[i] == 1) continue;
                if(i > 0 && nums[i] == nums[i-1] && used[i-1] == 0) continue;
                path.add(nums[i]);
                used[i] = 1;
                backtracking(nums, used);
                used[i] = 0;
                path.remove(path.size()-1);
            }
        }
    }
}
